1. The Field of the Invention.
This invention relates to systems and methods for managing the memory functions of a digital compputer. More specifically, the present invention is directed to an architecture for a dynamic memory management system for use in a digital computer and corresponding methods.
2. The Background Art.
In recent years, modern digial computers have become significantly more powerful and more complex than the digital computers of just a few years ago. Due to continuing advances in the fabrication of monolithic integrated circuits, and also advances in other technologies, digital computers are expected to become even more powerful and complex in the further. For example, as integrtated circuit for fabrication techniques are developed which allow more circuit elements to be placed onto a single microscopic chip of semiconductor material it becomes possible to dramatically increase the power of digital computers.
While computer hardware has become much more powerful in recent years, those who write computer software, and those who purchase such software, are always desiring more powerful hardware. It can always be expected that a computer programmer's designs, and a user's expectations, will be somewhat limited by the capacity of available hardware. Thus, there is a need to provide computer systems which will meet or exceed the performance requirements of software and the expectations of the users.
Two major parameters which are often used to determine the relative power and performance of a computer are: First, the amount of memory available to the programmer; and, second, the speed at which the computer is able to perform operations (i.e., the number of operations per second). The speed at which many computer systems are able to perform operations is often limited by the speed at which the computer's main memory may be accessed. Furthermore, computer systems that are limited by the size or performance of their memory are often characterized as being "memory bound". Since providing large amounts of memory is relatively expensive, it is important that the available memory be efficiently used.
It is possible to provide immense amounts of digital memory on magnetic or optical memory devices. However, writing data to, and reading data from, these inherently mechanical devices is a laboriously slow task (which is measured in milliseconds) compared to the speed of modern microprocessors which can perform an operation in 150 nanoseconds or less. Still further, the speed of operation of microprocessors is increasing every year. In contract to the performance increases in microprocessors, the gains in operating speed of mechanically operated magnetic and optical disk devices are achieved very slowly, are usually small gains, and come only after a concerted engineering effort.
In most computer systems, a central processing unit (CPU) communicates with a main memory to obtain instructions (often referred to as code) and to read and write data. The CPU accesses a specific main memory location by generating an address and placing that address on an address bus and then sending data to or receiving data from the specified memory location on a data bus. As mentioned previously, efficient use of main memory and speed of memory accesses are major factors affecting the performance of computer systems.
A memory management system, when incorporated into a digital computer, provides capabilities that allow more efficient use of main memory. These capabilities include translation of logical addresses assigned by the CPU (or generated by any other "logical address generating device") to physical addresses in main memory, providing multiple segregated address spaces for different processes residing in the computer, and protecting certain memory areas by allowing only read, write, or execute operations on those areas.
In order to provide the processes (a single computer system may handle many separate processes) residing in a computer system with a large number of logical memory locations within which to operate, while keeping the number of physical memory locations within practical limits, a virtual memory scheme is often used. A virtual memory scheme is commonly one in which the number of memory locations (represented by "logical addresses") which are available to a process is greater than the number of memory locations available in main memory (represented by "physical addresses"). Such virtual memory schemes make efficient use of main memory since any partcular process only requires access to small groups of code or data (hereinafter collectively referred to as "data") for short periods of time.
Thus, an important function of many memory management systems is providing virtual memory support. In this way, the CPU is allowed to access a larger logical memory space than is in fact physically present in main memory. In other words, a progrma or a process may have available to it a virtual memory space much greater than the physical or real memory space available in main memory.
In computer systems implementing a virtual memory scheme, the total amount of memory available to a particular process, for example 1 billion bytes (1 GBytes) , is usually stored on a magnetic disk device. A smaller amount of random access memory (RAM) , for example 1 million bytes (1 MBytes), is provided for the process in the main memory of the computer system. The data contained on the magnetic disk is moved into the limited space available in RAM as needed by the process. As the process finishes its use of a portion of data, that data is moved from the main memory to secondary storage and replaced by other data moved into the main memory.
The above-described virtual memory scheme is conventionally carried out by dividing the total virtual memory space (also referred to as "logical space") into many equal-sized units called "pages". All of the pages for a process are stored on a secondary storage device, such as a magnetic disk. The locations in physical memory which store the data from one page in logical memory space are referred to as a "frame". As pages of data are required by the CPU they are moved into a frame in the main memory.
Pages may remain in main memory or they may be moved back to secondary storage as determined by their frequency of usage and restrictions on the amount of available main (physical) memory. One usual function of a memory management system is to detect the CPU's attempted accesses to pages not currently present in main memory and causing the suspension of operation of the CPU until the page containing the demanded address has been moved into the main memory.
For example, in a computer system having a memory management system, each page may contain 2048 bytes. The individual memory locations in a page may be sequentially designated 0, 1, 2, 3, . . . 2046, 2047. A process generally accesses data stored in contiquous memory locations. That is, most processes would first access location 0, then location 1, and so on.
When the CPU requires data stored in locations 0, the entire page of data is moved from secondary storage (e.g., a magnetic disk) to the main memory. Such a transfer of data is a very slow process compared to the operating speed of the CPU. During the time that the page of data is being moved to main memory, the execution of the process is suspended and the CPU will generally wait for the requested data.
The task of identifying where data stored in secondary storage is moved to in the main memory is called "mapping". The term "mapping" may be used to describe the process in both memory management systems which do not implement a virtual memory scheme as well as those systems which do.
After a page of data has been moved to the main memory, the location of the page of data is then stored, or mapped, in a specialized memory area referred to as a translation memory. The CPU then, for example, would access the data at location 0 then location 1 until all of the data locations on that page through 2047 had been accessed . Then, if necessary, the CPU would cause the next page of data to be moved into the main memory where the sequence could begin again with an access to location 0 and continue through location 2047. In this way, it can appear to a process that 1 GByte of physical memory locations are available in the main memory while only a part of the data actually resides in the main memory at any one time.
One usual method of determining which pages are contained in main memory, and the location of those pages, at any instant in time is by use of a memory structure termed a translation table or a translation memory which may comprise one or more translation tables. The memory locations found in a translation table itself are referred to as "entries".
A primary function of a memory management system is to recognize a logical address from a logical address generating device, e.g., the CPU, as input and translate that logical address into a corresponding physical address in the main memory which is then output to the main memory. Normally, the translation table is stored in a high-speed random access memory (RAM) internal to the memory management system. The bit pattern of the logical address is used in some fashion to select an entry in the translation memory and the physical address translation stored at that entry is output from the memory management system.
The simplest form of this kind of memory management system is a direct mapped system where there exists an entry in the translation memory for every logical page in secondary storage. This memory management approach becomes impractical when the logical address space is very large, as is often the case in virtual memory schemes. Even when a large page size is chosen, such as 8 KBytes, each process would require 131, 072 entries in the translation table to provide a 1 GByte virtual address space. This is cost-prohibitive and inefficient since high-speed static RAM is expensive and the smallest allocable portion of physical memory main memory) would still be quite large.
A further limitation of direct mapped memory management systems can be seen when multiple processes must share the CPU and main memory. As the computer system inactivates one process to handle another process, various changes must occur within the data distributed throughout the computer system. The act of activating one process and deactivating another is commonly referred to as "context switching". Furthermore, the phrase "context switching time" is used to refer to the time required for the computer system to switch from one process, or context, to another.
Context switching in a direct mapped system requires that the entire contents of the translation table be reloaded as each process becomes active. An alternative to such a system would be to maintain several sets of translations, one for each process. However, this would require even more high speed RAM which will generally be cost prohibitive.
Another approach to memory management uses a fully associative translation look aside buffer. The translation look aside buffer is generally a small content addressable memory (CAM), usually containing only 16 or 32 entries. Each entry is comprised of a tag and a frame pointer. As the CPU generates a logical address, it is compared simultaneously to each of the tags stored in the translation look aside buffer.
If a translation entry which matches is found, the corresponding frame pointer contained in the entry is used as the physical address for the page. If no match is found, the memory management system causes the processor to suspend the memory access until the proper tag and frame pointer can be loaded into the translation look aside buffer, usually from a table in the main memory of the computer system. In some designs, the memory management system fetches the entry automatically and in others, the CPU must execute a software routine to fetch it.
Due to the complexity of content addressable memories, fully associative translation look aside buffer are of limited size, usually on larger than 32 entries. If a process accesses more than 32 pages over a short time period, now entries must be moved in to replace old entries, causing delays. Also, context switching to a new process requires that all translation look aside buffer entries be invalidated.
Yet another approach to memory management system design includes features of both direct mapped and fully associative designs. These are referred to as set associative memory management systems. These systems use a portion of the logical address to select an entry in the translation memory. The remaining portion of the logical address is compared to a tag in the selected translation table entry. If the logical address matches the tag, the frame pointer at that entry is used as the address of the frame in the main memory.
An enhancement to this design provides multiple entries, each with their own tag, which are compared simultaneously. These are referred to as "N-way set associative" memory management systems, where "N" is the number of entries in the simultaneously compared set. A set associative system can be partitioned to allow translations for several processes to reside in main memory at the same time, thus improving context switching speed.
A drawback of previously available N-way set associative memory management systems stems from the fact that the partitions provided in the main memory, and thus also the partitions provided in the translation tables, are fixed in size, regardless of the size of the process. This can leave many translation table entries unused if the process is small. Alternatively, if the process is large, too few translation table entries may be allocated for efficient operation.
Thus, it may be that a particular process requres only 64 frames in main memory (corresponding to 64 2 KByte pages of data) for efficient operation. However, in a conventional N-way set associative memory management system, the translation table may, for example, only be partitioned into areas representing 2048 pages. This is regardless of the fact that many processes might require 64 or fewer frames in main memory while other processes may require more than 2048 frames in main memory for efficient operation.
In view of the foregoing, it would be a significant advance in the art to provide a memory management system which provides entries that can be partitiioned so that only enough translation table entries (each entry representing a page in main memory) could be allocated to each process for efficient operation. It would be a further advance in the art to provide a memory management system which could be dynamically, i.e., "on the fly" or without any significant interruption in computer system operation, partitioned as processes are activated and deactivated.
It would be a further advance in the art to provide a memory management system which would allow the dynamic configuration of translation tables to be implemented by computer system managing software rather than requiring changes in hardware to reconfigure the translation tables. Another advance in the art would be to provide a dynamically configurable memory management unit which is able to translate a logical address to a physical address at a high speed, e.g., without requiring the CPU to "wait" for presentation of requested data from main memory.